package com.easy;

/**
 * Created by Lxk on 2020/2/23.
 */
public class Solution337 {

    /**
     * @param node
     * @param flag 表明上一层节点是否偷窃
     * @return
     */
    private int robValue(TreeNode node, boolean flag) {
        if (node == null) {
            return 0;
        } else {
            if (flag) {
                return robValue(node.left, false) + robValue(node.right, false);
            } else {
                int rob = robValue(node.left, true) + robValue(node.right, true) + node.val;
                int noRob = robValue(node.left, false) + robValue(node.right, false);
                return Math.max(rob, noRob);
            }
        }
    }

    public int rob(TreeNode root) {
        //虚拟上一个节点为已经偷窃
        int left = robValue(root, true);
        //虚拟上一个节点为未偷窃
        int right = robValue(root, false);
        return Math.max(left, right);
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(4);
        TreeNode node2 = new TreeNode(1);
        TreeNode node3 = new TreeNode(2);
        TreeNode node4 = new TreeNode(3);
        node.left = node2;
        node2.left = node3;
        node3.left = node4;
        Solution337 solution337 = new Solution337();
        System.out.println(solution337.rob(node));
    }

}
